1. Field of the Invention
The present invention generally relates to data communications, and more particularly, to an apparatus and method for performing multiple exclusive OR (XOR) operations using standard binary multiplication circuitry to create multiple XOR expressions simultaneously. The present invention is suited for performing calculations involving a large number of XOR operations with various combinations of product terms, such as cyclic redundancy check calculations.
2. Description of Related Art
Cyclic redundancy check (CRC) is a commonly known technique for determining transmission errors in communication systems. In digital data communication systems, bits of information often need to be transmitted from a transmitting location to a receiving location. Cyclic redundancy checking is a method of checking for errors in the data transmission over the communications link. For example when a block of data is to be transmitted, the sending device performs a calculation using either a 16 or 32 bit generator polynomial on the block to create a cyclic redundancy code (CRC) check. The resulting CRC check is then appended to the transmitted block. At the receiving device, the same calculation using the same polynomial is performed on the data block. If the computed CRC check result is the same as the appended CRC check, it is assumed that the data has been received successfully. If not, the sender can be notified to resend the block of data.
A Programmable Logic Device (PLD) is a semiconductor integrated circuit that contains fixed logic circuitry that can be programmed to perform a host of logic functions. In the semiconductor industry, PLDs are becoming increasingly popular for a number of reasons. Due to the advances of chip manufacturing technology, application specific integrated circuits (ASICs) designs have become incredibly complex. This complexity not only adds to design costs, but also the duration of time needed to develop an application specific design. To compound this problem, product life cycles are shrinking rapidly. As a result, it is often not feasible for original equipment manufacturers (OEMs) to design and use ASICs. OEMs are therefore relying more and more on PLDs. The same advances in fabrication technology have also resulted in PLDs with improved density and speed performance. Sophisticated programming software enables complex logic functions to be rapidly developed for PLDs. Furthermore, logic designs generally can also be easily migrated from one generation of PLDs to the next, further reducing product development times. The closing of the price-performance gap with ASICs and reduced product development times makes the use of PLDs compelling for many OEMs.
Most PLDs contain a two-dimensional row and column based architecture to implement custom logic. A series of row and column interconnects, typically of varying length and speed, provide signal and clock interconnects between blocks of logic on the PLD. The blocks of logic, often referred to by such names as Logic Elements (LEs), Adaptive Logic Modules (ALMs), or Complex Logic Blocks (CLBs), usually include one or more look up table (LUTs), programmable registers, adders and other circuitry to implement various logic and arithmetic functions. Many PLDs also include dedicated blocks of memory of various sizes for a variety of applications. Yet other PLDs include Digital Signal Processing (DSP) blocks for performing multiplication and other signal processing techniques such as finite input response filters or FIR filters. One commercially available PLD with blocks of logic, dedicated memory blocks, and DSP blocks is the Stratix II offered by Altera Corporation, San Jose, Calif. For more details on the Stratix II, see the “Stratix II Architecture”, Altera document number SII51002-4.0, Altera Corporation, December 2005, incorporated in its entirety by reference herein for all purposes.
In the aforementioned Stratix II device for example, the DSP blocks have circuitry for implementing multiplication, addition and subtraction. The PLD can be implemented into one of four modes of operation, including: (i) simple multiplier; (ii) multiply-accumulator; (iii) two-multipliers and an adder; and (iv) four-multipliers and an adder. In the modes having a multiplier and an adder, two numbers can be multiplied and then the product can be added/subtracted to a third number by the adder.
PLDs are often used for communication applications. A PLD can be configured as either a transmitter, a receiver, or a transceiver. Regardless if transmitting or receiving bits of information, the PLD will often have to perform a CRC operation to determine the integrity of the transmitted data. With current PLDs, the CRC operation is typically implemented using a large number of LUTs in the logic blocks provided on the device. This arrangement, however, is highly inefficient. The LUTs used for implementing the CRC function could otherwise be used for implementing other logic.
An apparatus and method for performing cyclical redundancy check calculations using the multiplication circuitry provided in the DSP blocks of a PLD is therefore needed.